package com.yuqian.JavaSe.leetcode.easy;

import java.util.HashSet;
import java.util.Set;

/**
 * Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
 * @author yuqian
 *判断一个数组是否含有相同的元素
 */
public class ContainsDuplicate {
	   public boolean containsDuplicate(int[] nums) {
		   //当数据量很大时不适合
	    /*    Arrays.sort(nums);
	        for(int i=1;i<nums.length;i++){
	        	if(nums[i-1]==nums[i]){
	        		return true;
	        	}
	        }
	        return false;*/
		   
		   Set<Integer> result = new HashSet<Integer>();
		   for(int i:nums){
			   if(!result.add(i)){
				   return true;
			   }
		   }
		   
		   
	        
	        return false;
	    }
	   /**
	    * 这个算法的思想是记录数组中的每一个值与另外一个值作比较，比较得到的差值为另外一个数组的下标，当这个下标出现两次就说明有两个重复的值。
	    * 这个算首先要找出数组中元素的大小范围，才能确定差值下标数组的大小，节约空间
	    * @author yuqian
	    *
	    */
	   public class Solution {
		    public boolean containsDuplicate(int[] nums) {
		        int min=Integer.MAX_VALUE;
		        int max=Integer.MIN_VALUE;
		        for(int b: nums){
		            if(b<min){
		                min=b;
		            }
		            if(b>max){
		                max=b;
		            }
		        }
		        boolean a[] = new boolean[max-min+1];
		        for(int b: nums){
		            if(a[b-min]){
		                return true;
		            }else{
		                a[b-min]=true;
		            }
		        }
		        return false;
		    }
		}
}
